/*
 * mergeSort.cpp
 *
 *  Created on: Sep 12, 2012
 *      Author: jeffrey
 */

#include<iostream>
#include<vector>
#include"../header/util.h"
using namespace std;
class MergeSort {
public:
	static void sort(int array[], int len) {
		mergeSort(array, 0, len - 1);
	}
private:
	static void mergeSort(int array[], int s, int e) {
		if (s < e) {
			int mid = (s + e) / 2;
			mergeSort(array, s, mid);
			mergeSort(array, mid + 1, e);
			merge(array, s, mid, e);
		}
	}
	static void merge(int array[], int s, int mid, int e) {
		int i = s, j = mid + 1;
		std::vector<int> buf(e - s + 1);
		int pos = 0;
		for (; i <= mid && j <= e;) {
			if (array[i] < array[j])
				buf[pos++] = array[i++];
			else
				buf[pos++] = array[j++];
		}
		for (; i <= mid; i++)
			buf[pos++] = array[i];
		for (; j <= e; j++)
			buf[pos++] = array[j];
		for (i = s; i <= e; i++)
			array[i] = buf[i - s];
		i = s;
		for (vector<int>::iterator it = buf.begin(); it != buf.end(); it++) {
			array[i++] = *it;
		}

	}
};
//int main() {
//	int a[]={3,5,1,-1,2,-9,0,0,9,-3,5,1};
//	MergeSort::sort(a,sizeof(a)/sizeof(int));
//	UtilFunc::printArray(a,sizeof(a)/sizeof(int));
//}
